home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 19 / CU Amiga Magazine's Super CD-ROM 19 (1998)(EMAP Images)(GB)[!][issue 1998-02].iso / CUCD / Programming / LEDA / man / b_priority_queue.tex < prev    next >
Encoding:
Text File  |  1994-08-05  |  1.1 KB  |  43 lines
  1.  
  2. {\magonebf 4.2 Bounded Priority Queues (b\_priority\_queue)}
  3.  
  4. \decl b\_priority\_queue K 
  5.  
  6. {\bf 1. Definition}
  7.  
  8. An instance $Q$ of the parameterized data type \name\ is a
  9. priority\_queue (cf.~section 4.1) whose information type is a 
  10. fixed interval $[a..b]$ of integers.
  11.  
  12.  
  13. \bigskip
  14. {\bf 2. Creation}
  15.  
  16. \create Q {(a,b)}
  17.  
  18. creates an instance \var\ of type \name\ with information type $[a..b]$
  19. and initializes it with the empty priority queue.
  20.  
  21.  
  22.  
  23. \bigskip
  24. {\bf 3. \operations }
  25.  
  26. The operations are the same as for the data type $priority\_queue$ with
  27. the additional precondition that any information argument must be
  28. in the range $[a..b]$.
  29.  
  30.  
  31. \bigskip
  32. {\bf 4. Implementation}
  33.  
  34. Bounded priority queues are implemented by arrays of linear lists.
  35. Operations insert, find\_min, del\_item, decrease\_inf, key, inf, 
  36. and empty take time $O(1)$, del\_min ( =  del\_item for the minimal
  37. element) takes time $O(d)$, where $d$ is the distance of the minimal
  38. element to the next bigger element in the queue ( = $O(b-a)$ in the
  39. worst case). clear takes time $O(b-a+n)$ and the space requirement is 
  40. $O(b-a+n)$, where $n$ is the current size of the queue.
  41.  
  42.  
  43.